#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;
const int maxn=300000, mods=998244353;
ll v[4*maxn+1][4], powt[maxn+1];
int to[4*maxn+1][4], a[maxn+1];

void initPow(int n) {
    powt[0] = 1;
    for (int i=1; i<=n; i++) powt[i] = powt[i-1]*2%mods;
}

inline int other(int a, int b) {return a!=1 && b!=1 ? 1 : (a!=2 && b!=2 ? 2 : 3);}

void change(int o, int l, int r, int t, int tv) {
    if (l==r) {
        for (int i=1; i<=3; i++) {
            if (tv==i) to[o][i]=i, v[o][i]=0;
            else to[o][i]=other(i, tv), v[o][i]=1;
        }
    } else {
        int mid=(l+r)/2;
        if (t<=mid) change(o*2, l, mid, t, tv);
        else change(o*2+1, mid+1, r, t, tv);
        for (int i=0; i<=3; i++) {
            to[o][i]=to[o*2][to[o*2+1][i]];
            v[o][i]=(v[o*2][to[o*2+1][i]]+v[o*2+1][i]*powt[mid-l+1]%mods)%mods;
        }
    }
}

ll solve(int o, int l, int r, int tl, int tr, int &t) {
    ll ret=0;
    if (l==tl && r==tr) ret=v[o][t], t=to[o][t];
    else {
        int mid=(l+r)/2;
        if (tr>mid) {
            if (tl<=mid) ret = (ret+solve(o*2+1, mid+1, r, max(tl, mid+1), tr, t)*powt[mid-tl+1]%mods)%mods;
                else ret = (ret+solve(o*2+1, mid+1, r, max(tl, mid+1), tr, t))%mods;
        }
        if (tl<=mid) ret = (ret+solve(o*2, l, mid, tl, min(tr, mid), t))%mods;
    }
    return ret;
}

int main() {
    freopen("practice.in", "r", stdin);
    freopen("practice.out", "w", stdout);

    int n, m;
    scanf("%d %d", &n, &m);
    initPow(n);
    for (int i=1; i<=n; i++) {
        scanf("%d", a+i);
        change(1, 1, n, i, a[i]);
    }

    for (int i=1; i<=m; i++) {
        int op, x, y;
        scanf("%d %d %d", &op, &x, &y);
        if (op==1) change(1, 1, n, x, a[x]=y);
        else {
            int t=a[y];
            printf("%lld\n", solve(1, 1, n, x, y, t));
        }
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}
